home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / comm / mail / Mutt089src.lha / Mutt-0.89i-AMIGA / src / rx / rxhash.c < prev    next >
C/C++ Source or Header  |  1998-01-28  |  9KB  |  395 lines
  1. /*    Copyright (C) 1995, 1996 Tom Lord
  2.  * 
  3.  * This program is free software; you can redistribute it and/or modify
  4.  * it under the terms of the GNU Library General Public License as published by
  5.  * the Free Software Foundation; either version 2, or (at your option)
  6.  * any later version.
  7.  * 
  8.  * This program is distributed in the hope that it will be useful,
  9.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  10.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11.  * GNU Library General Public License for more details.
  12.  * 
  13.  * You should have received a copy of the GNU Library General Public License
  14.  * along with this software; see the file COPYING.  If not, write to
  15.  * the Free Software Foundation, 59 Temple Place - Suite 330, 
  16.  * Boston, MA 02111-1307, USA. 
  17.  */
  18.  
  19.  
  20. /*
  21.  * Tom Lord (lord@cygnus.com, lord@gnu.ai.mit.edu)
  22.  */
  23.  
  24.  
  25. #include "rxall.h"
  26. #include "rxhash.h"
  27.  
  28.  
  29.  
  30. #ifdef __STDC__
  31. static struct rx_hash *
  32. default_hash_alloc (struct rx_hash_rules * rules)
  33. #else
  34. static struct rx_hash *
  35. default_hash_alloc (rules)
  36.      struct rx_hash_rules * rules;
  37. #endif
  38. {
  39.   return (struct rx_hash *)malloc (sizeof (struct rx_hash));
  40. }
  41.  
  42.  
  43. #ifdef __STDC__
  44. static struct rx_hash_item *
  45. default_hash_item_alloc (struct rx_hash_rules * rules, void * value)
  46. #else
  47. static struct rx_hash_item *
  48. default_hash_item_alloc (rules, value)
  49.      struct rx_hash_rules * rules;
  50.      void * value;
  51. #endif
  52. {
  53.   struct rx_hash_item * it;
  54.   it = (struct rx_hash_item *)malloc (sizeof (*it));
  55.   if (it)
  56.     {
  57.       it->data = value;
  58.       it->binding = 0;
  59.     }
  60.   return it;
  61. }
  62.  
  63.  
  64. #ifdef __STDC__
  65. static void
  66. default_free_hash (struct rx_hash * tab,
  67.             struct rx_hash_rules * rules)
  68. #else
  69. static void
  70. default_free_hash (tab, rules)
  71.      struct rx_hash * tab;
  72.      struct rx_hash_rules * rules;
  73. #endif
  74. {
  75.   free ((char *)tab);
  76. }
  77.  
  78.  
  79. #ifdef __STDC__
  80. static void
  81. default_free_hash_item (struct rx_hash_item * item,
  82.              struct rx_hash_rules * rules)
  83. #else
  84. static void
  85. default_free_hash_item (item, rules)
  86.      struct rx_hash_item * item;
  87.      struct rx_hash_rules * rules;
  88. #endif
  89. {
  90.   free ((char *)item);
  91. }
  92.  
  93. #ifdef __STDC__
  94. static int 
  95. default_eq (void * va, void * vb)
  96. #else
  97. static int 
  98. default_eq (va, vb)
  99.      void * va;
  100.      void * vb;
  101. #endif
  102. {
  103.   return va == vb;
  104. }
  105.  
  106.  
  107.  
  108. #define EQ(rules) ((rules && rules->eq) ? rules->eq : default_eq)
  109. #define HASH_ALLOC(rules) ((rules && rules->hash_alloc) ? rules->hash_alloc : default_hash_alloc)
  110. #define FREE_HASH(rules) ((rules && rules->free_hash) ? rules->free_hash : default_free_hash)
  111. #define ITEM_ALLOC(rules) ((rules && rules->hash_item_alloc) ? rules->hash_item_alloc : default_hash_item_alloc)
  112. #define FREE_HASH_ITEM(rules) ((rules && rules->free_hash_item) ? rules->free_hash_item : default_free_hash_item)
  113.  
  114.  
  115. static unsigned long rx_hash_masks[4] =
  116. {
  117.   0x12488421,
  118.   0x96699669,
  119.   0xbe7dd7eb,
  120.   0xffffffff
  121. };
  122.  
  123. /* hash to bucket */
  124. #define JOIN_BYTE(H, B)  (((H) + ((H) << 3) + (B)) & 0xf)
  125.  
  126. #define H2B(X) JOIN_BYTE (JOIN_BYTE (JOIN_BYTE ((X & 0xf), ((X>>8) & 0xf)), ((X>>16) & 0xf)), ((X>>24) & 0xf))
  127.  
  128. #define BKTS 16
  129.  
  130. /* Hash tables */
  131. #ifdef __STDC__
  132. struct rx_hash_item * 
  133. rx_hash_find (struct rx_hash * table,
  134.           unsigned long hash,
  135.           void * value,
  136.           struct rx_hash_rules * rules)
  137. #else
  138. struct rx_hash_item * 
  139. rx_hash_find (table, hash, value, rules)
  140.      struct rx_hash * table;
  141.      unsigned long hash;
  142.      void * value;
  143.      struct rx_hash_rules * rules;
  144. #endif
  145. {
  146.   rx_hash_eq eq = EQ (rules);
  147.   int maskc = 0;
  148.   long mask = rx_hash_masks [0];
  149.   int bucket = H2B(hash & mask);
  150.  
  151.   while (RX_bitset_member (&table->nested_p, bucket))
  152.     {
  153.       table = (struct rx_hash *)(table->children [bucket]);
  154.       ++maskc;
  155.       mask = rx_hash_masks[maskc];
  156.       bucket = H2B (hash & mask);
  157.     }
  158.  
  159.   {
  160.     struct rx_hash_item * it;
  161.     it = (struct rx_hash_item *)(table->children[bucket]);
  162.     while (it)
  163.       if (eq (it->data, value))
  164.     return it;
  165.       else
  166.     it = it->next_same_hash;
  167.   }
  168.  
  169.   return 0;
  170. }
  171.  
  172.  
  173. #ifdef __STDC__
  174. static int 
  175. listlen (struct rx_hash_item * bucket)
  176. #else
  177. static int 
  178. listlen (bucket)
  179.      struct rx_hash_item * bucket;
  180. #endif
  181. {
  182.   int i;
  183.   for (i = 0; bucket; ++i, bucket = bucket->next_same_hash)
  184.     ;
  185.   return i;
  186. }
  187.  
  188. #ifdef __STDC__
  189. static int
  190. overflows (struct rx_hash_item * bucket)
  191. #else
  192. static int
  193. overflows (bucket)
  194.      struct rx_hash_item * bucket;
  195. #endif
  196. {
  197.   return !(   bucket
  198.        && bucket->next_same_hash
  199.        && bucket->next_same_hash->next_same_hash
  200.        && bucket->next_same_hash->next_same_hash->next_same_hash);
  201. }
  202.  
  203.  
  204. #ifdef __STDC__
  205. struct rx_hash_item *
  206. rx_hash_store (struct rx_hash * table,
  207.            unsigned long hash,
  208.            void * value,
  209.            struct rx_hash_rules * rules)
  210. #else
  211. struct rx_hash_item *
  212. rx_hash_store (table, hash, value, rules)
  213.      struct rx_hash * table;
  214.      unsigned long hash;
  215.      void * value;
  216.      struct rx_hash_rules * rules;
  217. #endif
  218. {
  219.   rx_hash_eq eq = EQ (rules);
  220.   int maskc = 0;
  221.   long mask = rx_hash_masks [0];
  222.   int bucket = H2B(hash & mask);
  223.   int depth = 0;
  224.   
  225.   while (RX_bitset_member (&table->nested_p, bucket))
  226.     {
  227.       table = (struct rx_hash *)(table->children [bucket]);
  228.       ++maskc;
  229.       mask = rx_hash_masks[maskc];
  230.       bucket = H2B(hash & mask);
  231.       ++depth;
  232.     }
  233.   
  234.   {
  235.     struct rx_hash_item * it;
  236.     it = (struct rx_hash_item *)(table->children[bucket]);
  237.     while (it)
  238.       if (eq (it->data, value))
  239.     return it;
  240.       else
  241.     it = it->next_same_hash;
  242.   }
  243.   
  244.   {
  245.     if (   (depth < 3)
  246.     && (overflows ((struct rx_hash_item *)table->children [bucket])))
  247.       {
  248.     struct rx_hash * newtab;
  249.     newtab = (struct rx_hash *) HASH_ALLOC(rules) (rules);
  250.     if (!newtab)
  251.       goto add_to_bucket;
  252.     rx_bzero ((char *)newtab, sizeof (*newtab));
  253.     newtab->parent = table;
  254.     {
  255.       struct rx_hash_item * them;
  256.       unsigned long newmask;
  257.       them = (struct rx_hash_item *)table->children[bucket];
  258.       newmask = rx_hash_masks[maskc + 1];
  259.       while (them)
  260.         {
  261.           struct rx_hash_item * save = them->next_same_hash;
  262.           int new_buck = H2B(them->hash & newmask);
  263.           them->next_same_hash = ((struct rx_hash_item *)
  264.                       newtab->children[new_buck]);
  265.           ((struct rx_hash_item **)newtab->children)[new_buck] = them;
  266.           them->table = newtab;
  267.           them = save;
  268.           ++newtab->refs;
  269.           --table->refs;
  270.         }
  271.       ((struct rx_hash **)table->children)[bucket] = newtab;
  272.       RX_bitset_enjoin (&table->nested_p, bucket);
  273.       ++table->refs;
  274.       table = newtab;
  275.       bucket = H2B(hash & newmask);
  276.     }
  277.       }
  278.   }
  279.  add_to_bucket:
  280.   {
  281.     struct rx_hash_item  * it = ((struct rx_hash_item *)
  282.                  ITEM_ALLOC(rules) (rules, value));
  283.     if (!it)
  284.       return 0;
  285.     it->hash = hash;
  286.     it->table = table;
  287.     /* DATA and BINDING are to be set in hash_item_alloc */
  288.     it->next_same_hash = (struct rx_hash_item *)table->children [bucket];
  289.     ((struct rx_hash_item **)table->children)[bucket] = it;
  290.     ++table->refs;
  291.     return it;
  292.   }
  293. }
  294.  
  295.  
  296. #ifdef __STDC__
  297. void
  298. rx_hash_free (struct rx_hash_item * it, struct rx_hash_rules * rules)
  299. #else
  300. void
  301. rx_hash_free (it, rules)
  302.      struct rx_hash_item * it;
  303.      struct rx_hash_rules * rules;
  304. #endif
  305. {
  306.   if (it)
  307.     {
  308.       struct rx_hash * table = it->table;
  309.       unsigned long hash = it->hash;
  310.       int depth = (table->parent
  311.            ? (table->parent->parent
  312.               ? (table->parent->parent->parent
  313.              ? 3
  314.              : 2)
  315.               : 1)
  316.            : 0);
  317.       int bucket = H2B (hash & rx_hash_masks [depth]);
  318.       struct rx_hash_item ** pos
  319.     = (struct rx_hash_item **)&table->children [bucket];
  320.       
  321.       while (*pos != it)
  322.     pos = &(*pos)->next_same_hash;
  323.       *pos = it->next_same_hash;
  324.       FREE_HASH_ITEM(rules) (it, rules);
  325.       --table->refs;
  326.       while (!table->refs && depth)
  327.     {
  328.       struct rx_hash * save = table;
  329.       table = table->parent;
  330.       --depth;
  331.       bucket = H2B(hash & rx_hash_masks [depth]);
  332.       --table->refs;
  333.       table->children[bucket] = 0;
  334.       RX_bitset_remove (&table->nested_p, bucket);
  335.       FREE_HASH (rules) (save, rules);
  336.     }
  337.     }
  338. }
  339.  
  340. #ifdef __STDC__
  341. void
  342. rx_free_hash_table (struct rx_hash * tab, rx_hash_freefn freefn,
  343.             struct rx_hash_rules * rules)
  344. #else
  345. void
  346. rx_free_hash_table (tab, freefn, rules)
  347.      struct rx_hash * tab;
  348.      rx_hash_freefn freefn;
  349.      struct rx_hash_rules * rules;
  350. #en